
/**
 * 
 * 
 * 战场索敌
 * 
 * 题目描述

有一个大小是 N * M 的战场地图，被墙壁 '#' 分隔成大小不同的区域，上下左右四个方向相邻的空地 '.' 属于同一个区域，只有空地上可能存在敌人 'E”，请求出地图上总共有多少区域里的敌人数小于K。

输入描述
第一行输入为 N，M，K

N 表示地图的行数，M 表示地图的列数， K 表示目标敌人数量
N，M<=100
之后为一个 N * M 大小的字符数组。

输出描述
敌人数小于 K 的区域数量

用例
输入	3 5 2
..#EE
E.#E.
###..
输出	1
说明	地图被墙壁分为两个区域，左边区域有1个敌人，右边区域有3个敌人，符合条件的区域数量是1
 */

import java.util.LinkedList;
import java.util.Scanner;

/**
  * 
  题目解析 
用例图示如下



本题可以用深度优先搜索DFS来解决。

如果一个点满足下面条件，则进入深搜：

未被访问过（未被深搜过）
不是墙
同属一个源头的深搜区域，就是对应一个被墙隔开的独立区域，如果该独立区域深搜过程中，发现'E'，则该区域的敌军数量+1。

如果一个独立区域深搜完成，对应敌军数量<k，则最终题解统计的：敌军小于K的区域数量 + 1。

另外，本题数量级稍大，如果采用深度优先搜索（递归实现），则可能会发生栈内存溢出，即Stack Overflow，因此推荐广度优先搜索。

  */

public class 战场索敌 {
    
    static int n; // 地图行数
    static int m; // 地图列数
    static int k; // 区域敌军人数上限值
    static char[][] matrix; // 地图矩阵
    static boolean[][] visited; // 访问矩阵
    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 上、下、左、右偏移量
 
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
 
        visited = new boolean[n][m];
 
        matrix = new char[n][];
        
        for (int i = 0; i < n; i++) {
            matrix[i] = sc.next().toCharArray();
        }
 
        int ans = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 如果(i,j)位置未访问过，且不是墙，则进入广搜，广搜结果是广搜区域内的敌军数量，如果数量小于k，则该区域符合要求
                if (!visited[i][j] && matrix[i][j] != '#') {
                    ans += bfs(i, j) < k ? 1 : 0;
                }
            }
        }
 
        System.out.println(ans);
    }
 
    public static int bfs(int i, int j) {
        // 该区域敌军数量
        int count = 0;
 
        // 标记该位置访问过
        visited[i][j] = true;
 
        // 如果对应位置是E，则敌军数量+1
        if (matrix[i][j] == 'E') {
            count += 1;
        }
 
        // 广搜依赖于队列结构，先进先出
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(i * m + j);
 
        while (!queue.isEmpty()) {
            int pos = queue.removeFirst();
            int x = pos / m;
            int y = pos % m;
 
            // 遍历该位置的上下左右
            for (int[] offset : offsets) {
                int newX = x + offset[0];
                int newY = y + offset[1];
 
                // 如果新位置不越界，且未访问过，且不是墙，则继续广搜
                if (newX >= 0
                        && newX < n
                        && newY >= 0
                        && newY < m
                        && !visited[newX][newY]
                        && matrix[newX][newY] != '#') {
                    // 标记该位置访问过
                    visited[newX][newY] = true;
 
                    // 如果对应位置是E，则敌军数量+1
                    if (matrix[newX][newY] == 'E') {
                        count += 1;
                    }
 
                    queue.add(newX * m + newY);
                }
            }
        }
 
        return count;
    }

}
